package eulercycle;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.UnsupportedEncodingException;
import java.io.Writer;
import java.net.URLDecoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author iklyubanov
 */
class Graph {

    public static final String GRAPH_TEMPLATE_FILE = "\\graph_template.txt";
    public static final String GRAPH_CLASS_PATH = Graph.class.getProtectionDomain().getCodeSource().getLocation().getPath();
    private Map<String, List<String>> graph;
    public String[][] templateGraphElements = new String[][]{{"A", "B", "F"}, {"B", "A", "F", "E", "C"},
        {"C", "B", "F", "E", "D"}, {"D", "C", "E"},
        {"E", "D", "C", "B", "F"}, {"F", "E", "C", "B", "A"}};
    private static String charset = "Cp855";

    public boolean prepareGraph() {
        graph = new TreeMap<>();
        String[][] graphElements = null;
        try {
            graphElements = getGraphElements();
        } catch (NullPointerException ne) {
            System.out.println(ne.getMessage());
            return false;
        }
        graph = makeGraph(graphElements);

        return true;
    }

    public Map<String, List<String>> getGraphInstance() {
        if (graph == null) {
            prepareGraph();
        }
        return graph;
    }

    public String[][] getGraphElements() throws NullPointerException {
        String[][] graphElements = null;
        String fullPath = null;
        try {
            fullPath = prepareFullPath() + GRAPH_TEMPLATE_FILE;
        } catch (UnsupportedEncodingException ex) {
            Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, null, ex);
        }
        File file = new File(fullPath);
        if (!file.exists()) {
            try {
                file = createDefaultFile(file);
            } catch (IOException ex) {
                Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, null, ex);
            }
        }
        try {
            graphElements = parseFile(file);
        } catch (UnsupportedEncodingException ex) {
            Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, null, ex);
        } catch (FileNotFoundException ex) {
            Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, null, ex);
        } catch (IOException ex) {
            Logger.getLogger(Graph.class.getName()).log(Level.SEVERE, null, ex);
        }

        if (graphElements == null) {
            throw new NullPointerException("Error: Невозможно найти элементы эйлерова графа в файле!");
        }
        return graphElements;
    }

    public String prepareFullPath() throws UnsupportedEncodingException {
        String fullPath = null;
        try {
            fullPath = URLDecoder.decode(GRAPH_CLASS_PATH, "UTF-8").toString().replace("EulerCycle.jar", "");
        } catch (UnsupportedEncodingException ex) {
            throw new UnsupportedEncodingException("Error: Неизвестная кодировка файла " + GRAPH_CLASS_PATH);
        }
        return fullPath;
    }

    public File createDefaultFile(File file) throws IOException {

        try {
            if (file.exists()) {
                System.out.println("фаил " + file.getName() + " уже существует!");
                return file;
            }
            file.createNewFile();
        } catch (NullPointerException ne) {
            return null;
        }

        try (Writer writer = new PrintWriter(file)) {
            for (int i = 0; i < templateGraphElements.length; i++) {
                for (int j = 0; j < templateGraphElements[i].length; j++) {
                    writer.write(templateGraphElements[i][j] + " ");
                }
                writer.write("\n");
            }
            writer.flush();
        }
        return file;
    }

    public String[][] parseFile(File file) throws UnsupportedEncodingException, FileNotFoundException, IOException {
        String line = null;
        int i = 0, count = 0;
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), charset))) {
            while ((line = reader.readLine()) != null) {
                if (!line.trim().isEmpty()) {
                    count++;
                }
            }
        }
        String[][] elements = new String[count][];
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), charset))) {
            System.out.println("Первый элемент строки - вершина, следующие - смежные вершины");
            while ((line = reader.readLine()) != null) {
                line = line.trim();
                if (line.isEmpty()) {
                    continue;
                }
                if (line.contains(";")) {
                    elements[i] = line.split(";");
                } else {
                    elements[i] = line.split("\\s");
                }
                System.out.println("Вершины графа: " + Arrays.asList(elements[i]));
                i++;
            }
        }
        return elements;
    }

    /*
     * Сравнивает элементы 2 строковых массивов
     */
    public boolean compareGraphElements(String[][] a1, String[][] a2) {
        if (a1.length != a2.length) {
            return false;
        }

        for (int i = 0; i < a1.length; i++) {
            String[] el1 = a1[i];
            String[] el2 = a2[i];
            if (el1.length != el2.length) {
                return false;
            }
            for (int j = 0; j < el2.length; j++) {
                if (!el1[j].equals(el2[j])) {
                    return false;
                }
            }
        }
        return true;
    }

    public static Map<String, List<String>> makeGraph(String[][] graphElements) {
        Map<String, List<String>> graph = new TreeMap<String, List<String>>();
        for (int i = 0; i < graphElements.length; i++) {
            graph.put(graphElements[i][0], new ArrayList<String>(
                    Arrays.asList(Arrays.copyOfRange(graphElements[i], 1, graphElements[i].length))));
        }
        return graph;
    }

    public static void showGraph(Map<String, List<String>> graphs) {
        for (String key : graphs.keySet()) {
            System.out.println("вершина = '" + key + "' смежные вершины = " + graphs.get(key));
        }
    }

    public boolean isEulerGraph() {
        return isEulerGraph(graph);
    }

    /*
     * Проверяет граф на эйлеровость.(если какая-нибудь вершина имеет нечетное кол-во смежных вершин, то граф не эйлеров)
     */
    public static boolean isEulerGraph(Map<String, List<String>> graph) {
        for (String key : graph.keySet()) {
            int size = graph.get(key).size();
            if (size == 0 || size % 2 != 0) {
                System.out.println("Граф не является эйлеровым, количество ребер вершины " + key + " = " + size);
                return false;
            }
        }
        System.out.println("Граф является эйлеровым.");
        return true;
    }

    public String createEulerCycle() {
        return createEulerCycle(graph);
    }

    public String createEulerCycle(Map<String, List<String>> graph) {
        StringBuilder eulerCyclePath = new StringBuilder();
        String vertex = graph.entrySet().iterator().next().getKey();

        do {
            List<String> edges = graph.get(vertex);
            String nextVertex = null;
            if (graph.equals(this.graph)) {
                nextVertex = takeVertexWithMoreEdges(edges);
            } else {
                nextVertex = takeVertexWithMoreEdges(edges, graph);
            }
            if (nextVertex == null) {
                break;
            }
            eulerCyclePath.append(vertex).append("->").append(nextVertex).append("; ");
            graph.get(vertex).remove(nextVertex);
            graph.get(nextVertex).remove(vertex);
            vertex = nextVertex;
        } while (true);
        System.out.println("Эйлеров цикл: ");
        System.out.println(eulerCyclePath.toString());
        return eulerCyclePath.toString();
    }

    public String takeVertexWithMoreEdges(List<String> edges) {
        return takeVertexWithMoreEdges(edges, graph);
    }

    /*
     * Получить следующий элемент с большим кол-вом рёбер
     */
    public static String takeVertexWithMoreEdges(List<String> edges, Map<String, List<String>> graph) {
        boolean exceptBridges = true;
        String nextEdge = findNextVertex(edges, graph, exceptBridges);
        if (nextEdge == null) {
            exceptBridges = false;
            nextEdge = findNextVertex(edges, graph, exceptBridges);
        }
        return nextEdge;
    }

    /*
     * Находит следующую смежную вершину
     * @param exceptBridges - сначала среди вершин исключая мосты (выставлено <b>true</b>),
     * a потом вызываем метод с <b>false</b> и выбираем первый попавшийся мост
     */
    private static String findNextVertex(List<String> edges, Map<String, List<String>> graph, boolean exceptBridges) {
        String nextEdge = null;
        for (String edge : edges) {
            if (graph.get(edge).size() != 0) {
                if ((exceptBridges && graph.get(edge).size() > 1) || (!exceptBridges && graph.get(edge).size() == 1)) {
                    nextEdge = edge;
                    break;
                }
            }
        }
        return nextEdge;
    }
}